package com.mamingchao.basic.tanxin;

import org.springframework.util.CollectionUtils;

import java.util.Collections;
import java.util.Comparator;
import java.util.Objects;
import java.util.PriorityQueue;

/**
 * Created by mlamp on 2024/8/11.
 */
public class Greedy {



    public static void main(String[] args) {
//        int[] pokers = {99,200,21,30,100};
        int[] pokers = {2,5,7,3,100,0,1,4};
        int[] fenjintiao = {20, 30, 60, 10};

//        selectPoker(pokers, 0,3);
//        System.out.println("----------------------------------------------------");
//        int A_choose_max = selectPoker_A_first(pokers, 0, 3);
//        System.out.println(A_choose_max);

        int result = fenJinTiao(fenjintiao);
        System.out.println(result);
    }


    /**
     * 分金条
     * 时至今日，目前看这个题目，一定是每次切割，都把数组中最高的那一个切割出来，最省
     * @param demand 分金条 分法的 诉求与需求
     * @return
     */
    public static int fenJinTiao(int[] demand){

        if (Objects.isNull(demand) || demand.length == 0) {
            return 0;
        }

        int curCutCost = 0;
        PriorityQueue<Integer> heap = new PriorityQueue(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                return (Integer)o2 - (Integer)o1;
            }
        });
        for (int i = 0; i < demand.length; i++) {
            // sum
            curCutCost += demand[i];
            heap.add(demand[i]);
        }

        int totalCost = 0;
        while (heap.size() > 1) {
            // 当次切割出来的是数组里最大的
            totalCost += curCutCost;
            int curCut = heap.poll();
            System.out.println("切割出来的值为--" + curCut);
            curCutCost -= curCut;
        }
        System.out.println("切割出来的值为--" + heap.poll());

        return totalCost;
    }

    // 使用递归方式解决；A B两个人，分A先选和A后选两种情况
    // 当前函数为A先选的情况
    public static int selectPoker_A_first(int[] pokers, int L, int R){

        // base case; 当就剩下一个元素的时候，就返回当前元素即可
        if (L == R) {
            return pokers[L];
        }


        // 当A选择最左侧的情况；情况就是当前选择的最左侧的值，和选择完 最左侧后，剩下的 作为后选选手 可选的最优最大值
        int chooseLeft = pokers[L] + selectPoker_A_second(pokers, L + 1, R);
        // 当A选择最右侧的情况；情况就是当前选择的最右侧的值，和选择完 最右侧后，剩下的 作为后选选手 可选的最优最大值
        int chooseRight = pokers[R] + selectPoker_A_second(pokers, L , R - 1);


        return Math.max(chooseLeft, chooseRight);
    }

    // 当前函数为A后选的情况
    public static int selectPoker_A_second(int[] pokers, int L, int R){

        // base case; 当就剩下一个元素的时候，就返回当前元素即可
        if (L == R ) {
            return 0;
        }

        // 如果B选择最左侧的情况；情况就是当前选择的最左侧的值，和选择完 最左侧后，剩下的 作为后选选手 可选的最优最大值
        int chooseLeft = selectPoker_A_first(pokers, L + 1, R);
        //如果B选择最右侧的情况；情况就是当前选择的最右侧的值，和选择完 最右侧后，剩下的 作为后选选手 可选的最优最大值
        int chooseRight =  selectPoker_A_first(pokers, L , R - 1);

        // 当前轮次是B选择的轮次，以A选手为视角，肯定期望在该轮次，B的选择是最差选择才好
        return Math.min(chooseLeft, chooseRight);

    }

    public static void selectPoker(int[] pokers, int L, int R){

        // base case 1
        if (L == R) {
            System.out.println("选择了L--" + pokers[L]);
            return;
        }


        // L到R的范围，是这种情况[20,100,50]
        // 这个时候 L+1 == R-1;这个时候，选择 L 和 R里面，比较大的那一个就可以了，因为 不管怎么选，中间的都是下一个人的
        // base case 2
        if (L+1 >= R-1) {
            if (pokers[L] >= pokers[R]) {
                System.out.println("选择了L--" + pokers[L]);
                selectPoker(pokers, L+1, R);
            } else {
                System.out.println("选择了R--" + pokers[R]);
                selectPoker(pokers, L, R-1);
            }
            return;
        }


        // 判断 L+1 和 R-1 哪一侧的小，倾向选择哪一侧， 并计算 R-1 和L+1 的差值 v1
        // 判断 L 和 R 哪一侧的大，倾向选择哪一侧， 并计算 R 和L 的差值 v2
        // 判断 v1 和 v2 哪个大；v2大，倾向于 第二种选择； v1大，倾向于第一种选择
        // 这里整体思路，是贪心算法；A B两个人， 每个人计算的时候， 都看自己当前的选择，和用户下一步的选择；每次选择，自己一侧的利益最大化

        int v1 = pokers[R-1] - pokers[L+1];

        int v2 = pokers[R] - pokers[L];

        // 如果v1是正数， R-1 大，选 L侧
        // 如果v1是负数， L-1 大，选 R侧
        // 如果v2是正数， R 大，选 R侧
        // 如果v2是负数， L 大，选 L侧

        // 当 v1是正数，v2是负数，选L
        if (v1 >= 0 && v2 <= 0) {
            System.out.println("选择了L--" + pokers[L]);
            selectPoker(pokers, L+1, R);
        }

        // 当 v2是正数，v1是负数，选R
        if (v1 <= 0 && v2 >= 0) {
            System.out.println("选择了R--" + pokers[R]);
            selectPoker(pokers, L, R-1);
        }

        // 当 v1是正数，v2是正数，比较哪一侧的值更大
        if (v1 > 0 && v2 > 0) {
            if (v1 <= v2) {
                System.out.println("选择了R--" + pokers[R]);
                selectPoker(pokers, L, R-1);
            } else {
                // 当 v1 > v2的时候, 选择了L
                System.out.println("选择了L--" + pokers[L]);
                selectPoker(pokers, L+1, R);
            }
        }

        // 当 v1是负数，v2是负数，比较哪一侧的绝对值值更大
        if (v1 < 0 && v2 < 0) {
            if (v1 >= v2) {
                System.out.println("选择了L--" + pokers[L]);
                selectPoker(pokers, L+1, R);
            } else {
                // 当 v1 < v2的时候, 选择R
                System.out.println("选择了R--" + pokers[R]);
                selectPoker(pokers, L, R - 1);
            }
        }
    }


    public int firstChoose(int[] pokers, int L, int R) {
        if (L == R) {
            return pokers[L];
        }
        // 如果选择左侧
        int chooseL = pokers[L] + secondChoose(pokers, L+1, R);
        // 如果选择右侧
        int chooseR = pokers[R] + secondChoose(pokers, L, R-1);

        return Math.max(chooseL, chooseR);
    }


    public int secondChoose(int[] pokers, int L, int R) {
        if (L == R){
            return 0;
        }

        // 如果先手选择左侧
        int chooseL = pokers[L] + firstChoose(pokers, L+1, R);
        // 如果先手选择右侧
        int chooseR = pokers[R] + firstChoose(pokers, L, R-1);

        return Math.min(chooseL, chooseR);

    }
}
